Market based control requires allocating a task (e.g. physical actuation) among a large number of producers, with each producer bidding for part of the task. The task is determined by consumer agents in the system (higher level controllers or external requirements). Each producer has a supply curve reflecting the actuation or control produced as a function of price and each consumer has a demand curve indicating the actuation needed as a function of price. The equilibrium price is determined by the price at which aggregate demand and aggregate supply are equal. The price in turn determines what each individual actuator produces and individual consumer uses such that the total actuation equals the demanded actuation. As the task changes, different combinations of producers combine to collectively accomplish the task. Such a market is robust against failure of individual agents and changes in tasks, while requiring communication of only one quantity, namely the price, in order to coordinate the actions of an arbitrary and even time varying number of producers. Advantageously, such a price based market system naturally provides a Pareto optimal solution that is near optimal allocation within a degenerate array, even though the full optimization problem is NP-complete. Furthermore, reconciling conflicting goals is readily accomplished by having each individual actuator or consumer individually weight the conflicting goals. The market produces a group resolution between conflicting goals.
Unfortunately, presently available implementation schemes for market based control are impractical and scale poorly for large numbers of producers or consumers, especially when systems requiring real time actuation are considered. One could imagine, for example, connecting the producers and consumers using a bus (e.g. CAN bus, SPI, I2C or Ethernet bus) to communicate pricing information. For example, a 10 Mbit Ethernet system could be used to control 103 nodes of producers and consumers. Even using readily available off-the-shelf hardware, such a market control system is quite expensive, with per connection node costs of about $10 US dollars, for a total cost on the order of $10,000 US dollars. Moreover, due to the long packet header required, the bus would take on the order of 1–10 μsec to transmit a 10 bit number to each node, and then the same time to transmit the results back to each agent for one cycle of the market equilibration loop. If there are such 103 nodes, this would take on the order 2–20 msecs in the best case without packet collisions. Other widely available buses (e.g. CAN or SPI) would take at least an order of magnitude longer. The problem is even worse if multiple markets for competing allocations are required. For example, in object motion control both torques and forces must be allocated even though the requirements for each may conflict. If one had 10 markets to compute the supply and demand curves of competing allocations, either one would require 10 buses or the process would take on the order of seconds. There also is the issue of synchronizing the processors if a synchronous communication scheme is used.
In contrast to conventional digital control schemes, the present invention uses a high speed analog system minimally requiring only a single line (i.e. a “market wire”) interconnecting multiple producers and consumers in a given market. Analog electronic versions of markets allocate tasks such as actuation or control in a multi-producer and consumer system using correspondences set up between current and the quantity of a commodity and between the voltage and the price. The market consists of consumers removing current from a wire and producers adding current to the wire. The price is the voltage on the wire that eventually reaches an equilibrium price. This voltage, analogous to the equilibrium price, determines the current and hence the actuation produced by each actuator. As in the case of markets, the performance of the system is robust against failures and changes in actuators or tasks.
In one version of an analog system in accordance with the present invention, each consumer has a demand curve that decreases linearly as the voltage on the market wire increases and each producer, such as an actuator or controller, draws current from the wire that serves as the ‘market’. The conductances determine the slopes of the supply and demand curves as well as the market voltage. If some producers produce less, for example, actuation, less current is removed from the wire, the voltage rises causing more actuation from the remaining producers and reduces the demand by the consumers. Conversely, a decrease in demand (smaller conductances) causes less current to be added to the wire causing the market wire voltage to decrease. Production therefore decreases, and demand by the other consumers increases.
Implementation of the foregoing control schemes is of particular utility for problems requiring a large number of actuators to produce a desired actuation level. In this case there would be one consumer with a flat demand curve, i.e., a current source, for which the current (demand) does not change with voltage (price). The actuators (producer agents) would produce actuation such that all this current is removed to ground (demand balanced by supply). This high bandwidth, asynchronous coordination occurs through one wire and can be inexpensive per connection (only a few chips per node). No explicit computation is required to allocate the resources and a near optimal solution is obtained from a possibly degenerate set of equivalent solutions.
Advantageously, like traditional economic markets, analog circuit implementations of the present invention are robust against changes in actuator function or failures. As the cost per unit functionality of sensors, actuators, and computers (agents) continues to decrease, control systems comprised of many interconnected elements become increasingly practical. High speed systems having 103 processors with 10 market wires connected with multiplexed A/D's and D/A's or multiple op amp packages operating in real time are economically feasible using apparatus and methods of the present invention. Such systems could be much more responsive to events in their environment and internal states as well as exhibit robustness against component failure. Such an analog electronic implementation is distributed, flexible, easily extensible, efficiently uses wires, and reduces the communication load. Analog markets that can compute weighted sums of up to 104 spatially distributed agents and communicate the resulting sum back to agents in about 1–10 μsecs are supportable. The complexity of each such node is about 1–3 op amps per node or one embedded processor chip per node for the more flexible implementations.
In one preferred embodiment of the present invention, a distributed market based analog control system includes multiple producing units, each producing unit having an output responsive to a market price. Production levels are in part determined by needs of multiple consuming units, each consuming unit also having an input responsive to a market price. Communication of pricing information between the producing units and the consuming units is mediated by a marketwire connecting multiple producing units to multiple consuming units. Absolute or relative voltage level, current level, or frequency of voltage or current level changes can all be used to represent price information on the marketwire. For voltage level based pricing schemes, typically voltages of about 5–10 volts are used. Since noise based voltage fluctuations on the marketwire are typically less than about 1.0 mV, as much as 10 bits of precision is available for distinguishing price levels in the system. To simplify construction, reduce cost, and enhance system robustness, substantially identical adjustable circuit elements can be used for both multiple producing units and multiple consuming units, with the substantially identical voltage adjustable circuit elements being connected to the marketwire.
In a particularly preferred embodiment of the present invention, the distributed market based control system has no central controller for setting market prices. In the absence of either a central controller or a central timing mechanism, both of which can be expensive, prone to failure, or introduce substantial delays in price computation and distribution, the reliability of the system is improved. In operation, a producing unit having an output responsive to a market price, a consuming unit having an input responsive to a market price, are connected to a marketwire connecting the producing unit to the consuming unit with changes in analog electrical characteristics of the marketwire representing market price fluctuations. These analog electrical characteristics of the marketwire can be voltage level changes, current level changes, or time or frequency domain changes in electrical properties. Such a system operates asynchronously, without a central timing clock, with the marketwire immediately transmitting changes in price information on a microsecond scale, with no need for polling or n-way exchanges of information between n number of producers and consumers.
Advantageously, the present system for sharing pricing information between producers and consumers is not limited to electrical analog signals. Other analog propagating physical quantities can be used to compute the market and communicate pricing information. For example, a distributed market based analog control system including multiple producing units and multiple consuming units can be based on partitioning or distribution at least in part on non-electrical properties, including systems based singly or in combination on changes in electromechanical, mechanical, pressure, temperature, or thermal properties, chemical concentrations, light levels, or any other suitable physical property that allows for ready addition or subtraction of measurable system properties (e.g. by substitution of easily measurable fluid pressure changes in a closed pipeline system for voltage changes in wire circuits). Other physical characteristics suitable for communication of price include pressure within a cavity, magnetic flux within a superconducting loop, or optical energy within a resonant cavity.
As will be appreciated, since not all producers (consumers) are capable of providing a continuous range of actuation (demand) in response to a continuous range of received prices, some mechanism for handling stepped (or quantized) actuator response functions without introducing unwanted oscillations is needed. More generally, while it may not be possible to balance supply and demand exactly at each instance of time it can be possible to balance the time averaged supply and demand. The present invention provides such a mechanism by employment of an inventory or buffer unit to temporarily store excess output or demand and permit market equilibration. The inventory unit may be attached, along with producing units and consuming units, to a single marketwire or incorporated into individual or groups of producing and/or consuming units. In operation, for example, the inventory unit can inject additional charge, raise voltage level, or adjust vibrational amplitudes to smoothly equilibrate the market of consumers and producers.
Such inventory units are particularly useful in conjunction with on/off actuators such as valves. Most often instantaneous valve actuation cannot exact balance the instantaneous demand. For those embodiments of the invention having multiple valves, each of the multiple valves has a valve controller to control opening and closure of the multiple valves. A marketwire is connected to each valve controller to convey price information by analog fluctuations in electrical characteristics of the marketwire. Valves can be completely open and completely closed in certain embodiments, while valves controllable to partially open or close are possible in other embodiments. Valves can be used to control fluid flow (liquid or air), or even used to control radiant energy (e.g. light valves).
Multiple markets can be used to reconcile conflicting resource allocation, a problem that nearly always occurs in real systems. The present invention provides a smooth robust balance between conflicting goals. A market wire is established for each resource to be allocated. The actuators (producers) and consumers for each resource participate in a market that establishes a price for each resource. The utility curve for each agent (consumer or producer) that participates in more than one market, represents a weighted combination of each resource. The operation of the aggregate response to the various markets produces a robust, continuous, and optimal solution for conflicting resource allocation. The analogy to traditional economic markets such the allocation between apples and oranges, for example, is that each individuals utility curve expressing their preference for apples verses oranges at a given prices, determines not only how many apples and oranges an individual receives, but also how conflicting resource demands for apple and orange production are resolved.
In other embodiments of the invention, a distributed market based control assembly can be used in conjunction with fixed or movable structures. Typically multiple actuators are attached to the structure, with each of the multiple actuators having an actuator controller to control actuator applied force. Sensors are used for measuring structure movement, and a marketwire is connected to each actuator controller to convey price information to the actuator controllers by analog fluctuations in electrical characteristics of the marketwire. Actuators can be used to stabilize a fixed structure against movement, or alternatively can be used to control movement of movable structures from defined first positions to second positions (e.g. moving a robotic arm so its tip moves from point A to point B).
More generally, the present invention encompasses a control method for non-linear coupled systems of producing units having a single consumer output. The method of the invention includes the steps of setting each producing unit to have an output responsive to an analog signal representative of a market price, and connecting each producing unit to a marketwire, with the changes in the analog signal on the marketwire representing changes in the market price and output response of each producing unit.
Additional functions, objects, advantages, and features of the present invention will become apparent from consideration of the following description and drawings of preferred embodiments.